package array;

import org.junit.Test;

/**
 * @Description 面试题 10.01. 合并排序的数组 https://leetcode.cn/problems/sorted-merge-lcci/
 * @Author Firenut
 * @Date 2023-02-08 11:25
 */
public class T01_merge {
    @Test
    public void test() {
        merge2(new int[]{0}, 0, new int[]{0}, 1);
    }

    //
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1,j = n - 1,k = nums1.length - 1;
        while(j >= 0 && i >=0){
            if(nums1[i] > nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        while(i>=0) nums1[k--] = nums1[i--];
        while(j>=0) nums1[k--] = nums2[j--];
    }

    // 因为A数组尾部都是0，所以直接覆盖不会影响结果，通过比较 A,B有效部位的大小，较大者放入
    public void merge1(int[] A, int m, int[] B, int n) {
        int[] res = new int[A.length];
        int p1, p2, p3;
        p1 = m - 1;
        p2 = n - 1;
        p3 = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (A[p1] > B[p2]) {
                A[p3--] = A[p1--];
            } else {
                A[p3--] = B[p2--];
            }
        }
        while (p1 >= 0) {
            A[p3--] = A[p1--];
        }
        while (p2 >= 0) {
            A[p3--] = B[p2--];
        }
    }

    // 有点类似于归并排序，三个指针，取小者放入res数组
    public void merge(int[] A, int m, int[] B, int n) {
        int[] res = new int[A.length];
        int p1, p2, p3;
        p1 = p2 = p3 = 0;
        while (p1 < m && p2 < n) {
            if (A[p1] < B[p2]) {
                res[p3++] = A[p1++];
            } else {
                res[p3++] = B[p2++];
            }
        }
        while (p1 < m) {
            res[p3++] = A[p1++];
        }
        while (p2 < n) {
            res[p3++] = B[p2++];
        }
        for (int i = 0; i < A.length; i++) {
            A[i] = res[i];
        }
    }


}
